Networks are used to transfer voice, video and data between various network devices. Network devices such as switches are located within networks to direct the transfer of network traffic between various devices. Network traffic is typically bursty in nature. In order to compensate for network traffic bursts, memory queues are incorporated into network devices. These allow the device to temporarily sore traffic when the incoming rate is higher than an available outgoing rate. When more than one queue has traffic and each queue is contending for the same bandwidth, some of the traffic is required to wait in the queues and some mechanism, is needed to determine how traffic contention is resolved.
In order to resolve contention and provide a Quality of Service guarantee or some method of fair contention resolution to traffic, queue management algorithms must be implemented in the network devices. In one algorithm referred to as “priority queuing”, contending queues are assigned different priorities and traffic is forwarded from the queues in strict priority order. For example, referring to FIG. 1, four queues Q1, Q2, Q3 and Q4 (designated 1-4 respectively) hold packetised traffic that is to be forwarded on link (20). The link (20) has a finite bandwidth RL that must be shared by the traffic. To resolve the contention, the queues are prioritized and packets from the queues are forwarded to the link (20) in strict priority order under the control of a queue manager (10), such as a switch. While priority queuing works well when there is little contention, where there is contention traffic from higher priority queues is forwarded at the expense of traffic from lower priority queues. In this situation, traffic from high priority queues consume the majority of finite link bandwidth and lower priority queues are starved of bandwidth and back-up the network device architecture, potentially increasing latency to the point where packets are dropped. Dropped packets may require an entire stream to be retransmitted, thereby defeating the purpose of prioritising queues in the first place.
When traffic is to be carried in an ATM network a predetermined path called a “virtual, circuit” is agreed between an initiating end point and nodes within the network such that, for the duration of the connection, the agreed traffic from the end point can use that particular path. When the path is established, a “contract” is made by which the network agrees to carry the traffic and to meet any quality of service and minimum bandwidth guarantees so long as the traffic stays within specified traffic descriptors. Traffic in an ATM network is formatted into equal sized cells or packets.
Where a number of links are to contend for bandwidth, on a single outgoing link, it is quite likely that some of the links will have an agreed contract for a proportion of the outgoing link's bandwidth. However, it is also quite likely that other links without contracted bandwidth on the outgoing link may also require access to the link. These are accepted on a “best-effort” basis, the outgoing link giving any uncontracted bandwidth to these links. Obviously, multiplexing of the traffic streams from the links onto the outgoing link must be managed in a fair way whilst satisfying the established contracts. Fair sharing algorithms and round-robin type algorithms are based primarily on priority levels determined in dependence on the contracted bandwidth for each link. Thus, links without specific contracted bandwidth, such as those that have been accepted on a “best effort” basis are ignored whilst there is traffic pending in contracted links or whilst it is a contracted link's turn to transmit on the outgoing link. One way that has been suggested to overcome this problem is to give those links that are not contracted a weight corresponding to a low priority so that the links are multiplexed onto whatever remains after the contracted links are multiplexed onto the link. However, such an arbitrary assignment of bandwidth does not result in efficient sharing of the outgoing link. Furthermore, bandwidth on the outgoing link is reserved for each link in dependence of its weight, irrespective of whether that link has anything to transmit. Thus, a high priority link without any data to transmit takes up bandwidth on the outgoing link that could be used to transmit data from the uncontracted links.
One algorithm that attempts to resolve issues surrounding contention management without the above problems is “Weighted Fair Queuing” (WFQ). Contending queues are assigned weights and packets are forwarded from queues in proportion to the weights assigned to each queue. For example, referring again to FIG. 1, if the queue manager (10) was a Weighted Fair queue controller, the four queues would be assigned a weight that represents the amount of bandwidth that is reserved for that queue. If the total available bandwidth of the link were 100 bytes per second, then with queue weights assigned as 20%, 25%, 15% and 40% to Q1, Q2, Q3 and Q4 respectively, Q1 would be allocated 20 bytes per second on the link, Q2 would be allocated 25 bytes per second, Q3 15 bytes per second and Q4 40 bytes per second. The queue manager ensures queues have fair access to the outgoing link whilst satisfying the allocated bandwidths. In one implementation of the weighted fair queue algorithm, a linear array is defined. Each array element represents a transmission time on the outgoing link. Queues are scheduled by linking them to one of the elements in the array, the order of transmission being determined by the order of the queues in the array. Once a transmission is made from a queue according to the schedule, the position of the queue within the array is recalculated. The recalculation schedules the queue further along the array, the exact position being calculated in dependence on the queues assigned weight.
Whilst the basic Weighted Fair Queue algorithm works well for preventing starvation that occurs in priority queuing and establishes a maximum flow rate for each queue, link bandwidth is still wasted because the percentage of link bandwidth is reserved for a particular queue is reserved whether or not there are packets, waiting. Furthermore, there is no apparent way of distributing excess bandwidth between other queues because queues do not have priority assigned relative to one another.
In the past, the above problem is usually approached by the implementation of a scheduler based on a linear array, such as that for the weighted fair queue scheduler discussed above. However, one problem with such an approach is that in order to obtain a high granularity (granularity is a measurement of the minimum ban width division of the outgoing link that can be allocated) the array must be made very large. This is because the size of the array determines the minimal bandwidth (if the array is of size N, the minimum bandwidth supported will be 1/N*(ink Rate)). This is a particular problem in real-time devices since the addition of a new stream requires the whole array needs to be reconfigured, a task which could be impossible to perform without interrupting transmission scheduling for large periods of time.